#include "stdafx.h"
#include "SpeaWithConnectivity.h"
#include "Graph.h"

SpeaWithConnectivity::SpeaWithConnectivity(Topology* pTopology, As* pVictim, As* pAttacker) : 
Attack(CreateSpeaMsg(pTopology, pVictim, pAttacker), CreateWhoToSendTo(pTopology, pVictim, pAttacker)),
_topology(pTopology)
{
}

SpeaWithConnectivity::~SpeaWithConnectivity()
{
}

Set<As*>* SpeaWithConnectivity::CreateWhoToSendTo(Topology* pTopology, As* pVictim, As* pAttacker)
{
	//if (_firstHopInSpeaMsg == 0)
	//{
	CreateSpeaMsg(pTopology, pVictim, pAttacker);
	//}
	Set<Vertex*>* neighbors = new Set<Vertex*>();
	pAttacker->GetNeighbors(neighbors);

	if (_firstHopInSpeaMsg != 0)
	{
		Set<Vertex*>::iterator it;
		it = neighbors->find(_firstHopInSpeaMsg);
		neighbors->erase(it);
	}

	Set<As*>* result = reinterpret_cast<Set<As*>*>(neighbors);
	return result;
}

BgpMessage* SpeaWithConnectivity::CreateSpeaMsg(Topology* pTopology, As* pVictim, As* pAttacker)
{
	//if (_firstHopInSpeaMsg == 0)
	//{
	_topology = pTopology;
	max_weight = 5000;

	Map<As*, Vector<As*> >* pathToVictim = new Map<As*, Vector<As*> >();
	Map<Vertex*, SpeaWithConnectivity::weight_t> * min_distance = new Map<Vertex*, SpeaWithConnectivity::weight_t>();
	Map<Vertex*, Vertex*> *previous = new Map<Vertex*, Vertex*>();

	DijkstraComputePaths(pAttacker, min_distance, previous);

	Vector<As*> path = DijkstraGetShortestPathTo(pVictim, previous);

	Pair<As*, Vector<As*> >* pairToInsert = new Pair<As*, Vector<As*> >(pVictim, path);
	pathToVictim->insert(*pairToInsert);

	BgpMessage* msg = new BgpMessage(pathToVictim);

	_firstHopInSpeaMsg = (path.size() > 0) ? path.front() : 0;
	//if (path.size() > 0)
	//{
	//	_firstHopInSpeaMsg = path.front();
	//}
	//else
	//{
	//	_firstHopInSpeaMsg = 0;
	//}
	_msg = msg;
	//}
	return _msg;
}


void SpeaWithConnectivity::DijkstraComputePaths(Vertex* source,
	Map<Vertex*, weight_t> *min_distance,
	Map<Vertex*, Vertex*> *previous)
{
	//int n = adjacency_list.Vertices.size();
	min_distance->clear();
	//min_distance.resize(n, max_weight);
	(*min_distance)[source] = 0;
	previous->clear();
	//previous.resize(n, -1);
	Set<Pair<weight_t, Vertex*> > vertex_queue;

	weight_t* minDistanceToSource = new weight_t((*min_distance)[source]);
	Pair<weight_t, Vertex*>* pairToInsert = new Pair<weight_t, Vertex*>((*min_distance)[source], source);
	vertex_queue.insert(*pairToInsert);

	while (!vertex_queue.empty())
	{
		weight_t dist = vertex_queue.begin()->first;
		Vertex* u = vertex_queue.begin()->second;
		vertex_queue.erase(vertex_queue.begin());

		// Visit each edge exiting u
		//Set<Vertex*> tempNeighbors = ;
		Set<Vertex*>* neighbors = new Set<Vertex*>();
		u->GetNeighbors(neighbors);
		for (Set<Vertex*>::iterator neighbor_iter = neighbors->begin();
			neighbor_iter != neighbors->end();
			neighbor_iter++)
		{
			Vertex* v = *neighbor_iter;
			weight_t weight = 1;
			weight_t distance_through_u = dist + weight;
			weight_t known_distance_to_v = min_distance->find(v) == min_distance->end() ? max_weight : min_distance->at(v);
			if (distance_through_u < known_distance_to_v) {

				Pair<weight_t, Vertex*>* pairToErase = new Pair<weight_t, Vertex*>((*min_distance)[v], v);
				vertex_queue.erase(pairToErase);

				(*min_distance)[v] = distance_through_u;
				(*previous)[v] = u;

				Pair<weight_t, Vertex*>* newPairToInsert = new Pair<weight_t, Vertex*>(distance_through_u, v);
				vertex_queue.insert(*newPairToInsert);
			}
		}
	}
}


Vector<As*> SpeaWithConnectivity::DijkstraGetShortestPathTo(Vertex* vertex,
	Map<Vertex*, Vertex*> *previous)
{
	Vector<As*>  path = Vector<As*>();
	for (; previous->find(vertex) != previous->end(); vertex = previous->at(vertex))
	{
		path.push_back((As*)(vertex));
	}

	Vector<As*>* result = new Vector<As*>();
	if (path.size() > 0)
	{
		Vector<As*>::iterator pathIter;
		for (pathIter = path.end() - 1; pathIter != path.begin(); --pathIter)
		{
			result->push_back(*pathIter);
		}
		result->push_back(*path.begin());
	}
	return *result;
}


